#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
using namespace std;

  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };

class Solution {
public:
    ListNode* mergesort(vector<ListNode*>& lists, int begin, int end) {
        if (begin > end)
            return nullptr;
        if (begin == end)
            return lists[begin];
        int mid = (begin + end) >> 1;
        ListNode* pcur1 = mergesort(lists, begin, mid);
        ListNode* pcur2 = mergesort(lists, mid + 1, end);
        // int cur1 = begin,cur2 = mid+1;
        ListNode newhead;
        ListNode* prev = &newhead;

        if (pcur1 == nullptr) return pcur2;
        if (pcur2 == nullptr) return pcur1;

        while (pcur1 && pcur2) {
            if (pcur1->val < pcur2->val) {
                prev->next = pcur1;
                prev = pcur1;
                pcur1 = pcur1->next;
            }
            else {
                prev->next = pcur2;
                prev = pcur2;
                pcur2 = pcur2->next;
            }
        }
        if (pcur1)
            prev->next = pcur1;
        if (pcur2)
            prev->next = pcur2;
        return newhead.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergesort(lists, 0, lists.size() - 1);
    }
};